package leetcode.editor.cn.dsa02_linkedlist;
//给你两个二进制字符串，返回它们的和（用二进制表示）。
//
// 输入为 非空 字符串且只包含数字 1 和 0。 
//
// 
//
// 示例 1: 
//
// 输入: a = "11", b = "1"
//输出: "100" 
//
// 示例 2: 
//
// 输入: a = "1010", b = "1011"
//输出: "10101" 
//
// 
//
// 提示： 
//
// 
// 每个字符串仅由字符 '0' 或 '1' 组成。 
// 1 <= a.length, b.length <= 10^4 
// 字符串如果不是 "0" ，就都不含前导零。 
// 
// Related Topics 数学 字符串 
// 👍 521 👎 0

public class AddBinary67 {
    public static void main(String[] args) {
        Solution solution = new AddBinary67().new Solution();
        String s = solution.addBinary("11", "1");
        System.out.println("11 + 1 = " + s);
        String s2 = solution.addBinary("1010", "1011");
        System.out.println("1010 + 1011 = " + s2);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String addBinary(String a, String b) {
            StringBuilder sb = new StringBuilder();
            int array = 0; // 记录进位
            // 1.倒序遍历字符串的每一位进行相加运算
            for (int i = a.length() - 1, j = b.length() - 1;
                 i >= 0 || j >= 0; i--,j--) {
                 int x = i >= 0 ? a.charAt(i) - '0' : 0;
                 int y = j >= 0 ? b.charAt(j) - '0' : 0;
                // 对应位置的数值相加
                int sum = x + y + array;
                array = sum / 2; // 计算进位
                int num = sum % 2; // 需要保存的结果值
                // 保存结果
                sb.append(String.valueOf(num));
            }
            // 2.最高位发生进位
            if (array > 0) {
                sb.append("1");
            }
            // 3.字符串反转
            return sb.reverse().toString();
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}